lib/Mi manual de algoritmos/version_actual/src/grafos/ford_fulkerson.cpp

   1 /*
   2   cap[i][j] = Capacidad de la arista (i, j).
   3   prev[i] = Predecesor del nodo i en un camino de aumentación.
   4  */
   5 int cap[MAXN+1][MAXN+1], prev[MAXN+1];
   6
   7 vector<int> g[MAXN+1]; //Vecinos de cada nodo.
   8 inline void link(int u, int v, int c)
   9 { cap[u][v] = c; g[u].push_back(v), g[v].push_back(u); }
  10 /*
  11   Notar que link crea las aristas (u, v) && (v, u) en el grafo
  12   g. Esto es necesario porque el algoritmo de Edmonds-Karp
  13   necesita mirar el "back-edge" (j, i) que se crea al bombear
  14   flujo a través de (i, j). Sin embargo, no modifica
  15   cap[v][u], porque se asume que el grafo es dirigido. Si es
  16   no-dirigido, hacer cap[u][v] = cap[v][u] = c.
  17 */
  18
  19
  20 /*
  21   Método 1:
  22
  23   Mantener la red residual, donde residual[i][j] = cuánto
  24   flujo extra puedo inyectar a través de la arista (i, j).
  25
  26   Si empujo k unidades de i a j, entonces residual[i][j] -= k
  27   y residual[j][i] += k (Puedo "desempujar" las k unidades de
  28   j a i).
  29
  30   Se puede modificar para que no utilice extra memoria en la
  31   tabla residual, sino que modifique directamente la tabla
  32   cap.
  33 */
  34
  35 int residual[MAXN+1][MAXN+1];
  36 int fordFulkerson(int n, int s, int t){
  37   memcpy(residual, cap, sizeof cap);
  38
  39   int ans = 0;
  40   while (true){
  41     fill(prev, prev+n, -1);
  42     queue<int> q;
  43     q.push(s);
  44     while (q.size() && prev[t] == -1){
  45       int u = q.front();
  46       q.pop();
  47       vector<int> &out = g[u];
  48       for (int k = 0, m = out.size(); k<m; ++k){
  49         int v = out[k];
  50         if (v != s && prev[v] == -1 && residual[u][v] > 0)
  51           prev[v] = u, q.push(v);
  52       }
  53     }
  54
  55     if (prev[t] == -1) break;
  56
  57     int bottleneck = INT_MAX;
  58     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  59       bottleneck = min(bottleneck, residual[u][v]);
  60     }
  61     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  62       residual[u][v] -= bottleneck;
  63       residual[v][u] += bottleneck;
  64     }
  65     ans += bottleneck;
  66   }
  67   return ans;
  68 }
  69
  70
  71
  72 /*
  73   Método 2:
  74
  75   Mantener la red de flujos, donde flow[i][j] = Flujo que,
  76   err, fluye de i a j. Notar que flow[i][j] puede ser
  77   negativo. Si esto pasa, es lo equivalente a decir que i
  78   "absorbe" flujo de j, o lo que es lo mismo, que hay flujo
  79   positivo de j a i.
  80
  81   En cualquier momento se cumple la propiedad de skew
  82   symmetry, es decir, flow[i][j] = -flow[j][i]. El flujo neto
  83   de i a j es entonces flow[i][j].
  84 */
  85
  86 int flow[MAXN+1][MAXN+1];
  87 int fordFulkerson(int n, int s, int t){
  88   //memset(flow, 0, sizeof flow);
  89   for (int i=0; i<n; ++i) fill(flow[i], flow[i]+n, 0);
  90   int ans = 0;
  91   while (true){
  92     fill(prev, prev+n, -1);
  93     queue<int> q;
  94     q.push(s);
  95     while (q.size() && prev[t] == -1){
  96       int u = q.front();
  97       q.pop();
  98       vector<int> &out = g[u];
  99       for (int k = 0, m = out.size(); k<m; ++k){
 100         int v = out[k];
 101         if (v != s && prev[v] == -1 && cap[u][v] > flow[u][v])
 102           prev[v] = u, q.push(v);
 103       }
 104     }
 105
 106     if (prev[t] == -1) break;
 107
 108     int bottleneck = INT_MAX;
 109     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
 110       bottleneck = min(bottleneck, cap[u][v] - flow[u][v]);
 111     }
 112     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
 113       flow[u][v] += bottleneck;
 114       flow[v][u] = -flow[u][v];
 115     }
 116     ans += bottleneck;
 117   }
 118   return ans;
 119 }
 120